#include<iostream>
#include<queue>
#include<stdio.h>

using namespace std;
#define K 3
#define RADIX 10

queue<int>Q[RADIX];

void Printarry(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}

//获取基准值
int Getkey(int value, int k)
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}

	return key;
}

void Distribute(int* arr, int left, int right, int k)
{
	for (int i = left; i <= right; i++)
	{
		int key = Getkey(arr[i], k);
		Q[key].push(arr[i]);

	}
}

void Collect(int* arr)
{
	int j = 0;
	for (int i = 0; i < RADIX; i++)
	{
		while (!Q[i].empty())
		{
			arr[j++]=Q[i].front();
			Q[i].pop();
		}
	}
}

void RadixSort(int* arr, int left, int right)
{
	for (int i = 0; i < K; i++)
	{
		//分发数据
		Distribute(arr, left, right, i);

		//回收数据
		Collect(arr);
	}
}


int main()
{
	int arr[] = { 278,109,63,930,589,184,505,269,8,83 };
	int n = sizeof(arr) / sizeof(arr[0]);

	Printarry(arr, n);

	RadixSort(arr, 0, n - 1);

	Printarry(arr, n);

	return 0;
}